# LeetCode 125、验证回文串

# 一、题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

**说明：**本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: "race a car"
输出: false
解释："raceacar" 不是回文串

提示：

1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成

# 二、题目解析

具体操作如下：

1、设置左右两个指针，分别指向字符串的开头位置和结束位置。

2、移动和观察者两个指针所指向元素之间的关系。

3、如果 left 指向的元素不是字母、也不是数字，那么可以忽略掉这个元素，即让 left 向右移动。

4、如果 right 指向的元素不是字母、也不是数字，那么可以忽略掉这个元素，即让 right 向左移动。

5、进过 3、4 操作后，要么 left 和 right 相遇了，跳出循环；要么 left 和 right 还没有相遇，并且它们都是指向字母或者数字。

6、只需要判断一下 left 和 right 指向的元素值是否相同就行，如果不相同，直接返回 false。

7、否则，继续让两个指针向内移动，left 向右移动，right 向左移动。

8、最后，没有得到 false 的答案就说明是回文串，返回 true

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 验证回文串（LeetCode 125）：https://leetcode.cn/problems/valid-palindrome/submissions/
class Solution {
    public boolean isPalindrome(String s) {

        // 设置左右两个指针
        int left = 0 ;
        
        int right = s.length() - 1 ;


        // 移动和观察者两个指针所指向元素之间的关系
        while (left < right) {
            
            // 这里的逻辑有点像快速排序的代码

            // 如果 left 指向的元素不是字母、也不是数字
            // 那么可以忽略掉这个元素，即让 left 向右移动
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                // left 向右移动
                left++;

            }

            // 如果 right 指向的元素不是字母、也不是数字
            // 那么可以忽略掉这个元素，即让 right 向左移动
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                // right 向左移动
                right--;

            }

            // 来到这里时
            // 要么 left 和 right 相遇了，跳出循环
            // 要么 left 和 right 还没有相遇，并且它们都是指向字母或者数字
            if (left < right) {

                // 只需要判断一下 left 和 right 指向的元素值是否相同就行
                // 题目说明 可以忽略字母的大小写
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    // 不相同就直接说明不是回文串
                    return false;
                }

                // 否则，继续让两个指针向内移动

                // left 向右移动
                left++;

                // right 向左移动
                right--;
            }
        }

        // 最后，没有得到 false 的答案就说明是回文串，返回 true
        return true;
    }
}

# 2、C++ 代码

class Solution {
public:
    bool isPalindrome(string s) {
        // 设置左右两个指针
        int left = 0 ;
        
        int right = s.size() - 1 ;


        // 移动和观察者两个指针所指向元素之间的关系
        while (left < right) {
            
            // 这里的逻辑有点像快速排序的代码

            // 如果 left 指向的元素不是字母、也不是数字
            // 那么可以忽略掉这个元素，即让 left 向右移动
            while (left < right && !isalnum(s[left])) {
                // left 向右移动
                left++;

            }

            // 如果 right 指向的元素不是字母、也不是数字
            // 那么可以忽略掉这个元素，即让 right 向左移动
            while (left < right && !isalnum(s[right])) {
                // right 向左移动
                right--;

            }

            // 来到这里时
            // 要么 left 和 right 相遇了，跳出循环
            // 要么 left 和 right 还没有相遇，并且它们都是指向字母或者数字
            if (left < right) {

                // 只需要判断一下 left 和 right 指向的元素值是否相同就行
                // 题目说明 可以忽略字母的大小写
                if (tolower(s[left]) != tolower(s[right])) {
                    // 不相同就直接说明不是回文串
                    return false;
                }

                // 否则，继续让两个指针向内移动

                // left 向右移动
                left++;

                // right 向左移动
                right--;
            }
        }

        // 最后，没有得到 false 的答案就说明是回文串，返回 true
        return true;

    }
};

# 3、Python 代码

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 设置左右两个指针
        left = 0 
        
        right = len(s) - 1 


        # 移动和观察者两个指针所指向元素之间的关系
        while left < right : 
            
            # 这里的逻辑有点像快速排序的代码

            # 如果 left 指向的元素不是字母、也不是数字
            # 那么可以忽略掉这个元素，即让 left 向右移动
            while  left < right and not s[left].isalnum():
                # left 向右移动
                left += 1

            

            # 如果 right 指向的元素不是字母、也不是数字
            # 那么可以忽略掉这个元素，即让 right 向左移动
            while left < right and not s[right].isalnum():
                # right 向左移动
                right -= 1

        

            # 来到这里时
            # 要么 left 和 right 相遇了，跳出循环
            # 要么 left 和 right 还没有相遇，并且它们都是指向字母或者数字
            if left < right :

                # 只需要判断一下 left 和 right 指向的元素值是否相同就行
                # 题目说明 可以忽略字母的大小写
                if s[left].lower() != s[right].lower():
                    # 不相同就直接说明不是回文串
                    return False
                

                # 否则，继续让两个指针向内移动

                # left 向右移动
                left += 1

                # right 向左移动
                right -= 1
    
        # 最后，没有得到 false 的答案就说明是回文串，返回 true
        return True
class Solution:
    def isPalindrome(self, s: str) -> bool:

        # isalnum() 方法检测字符串是否由字母和数字组成
        # 转换为字符串数组的形式
        xArray = "".join(ch.lower() for ch in s if ch.isalnum())

        # 左边索引的位置在 0 
        left = 0

        # 右边索引的位置在 len(xArray) - 1
        right = len(xArray) - 1

        # 两个索引向内移动
        # left 向右移动
        # right 向左移动
        while left <= right:
            # 判断这两个元素值是否相同
            if xArray[left] != xArray[right]:
                # 如果不同，直接返回 False
                return  False

            # 否则，left 向右移动
            left += 1
        
            # right 向左移动
            right -= 1
        
        return True

# 四、复杂度分析

时间复杂度：O(|s|)，其中 |s| 是字符串 s 的长度。
空间复杂度：O(1)。

← LeetCode 9 、回文数 LeetCode 143、重排链表 →